#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
    /**
     * @brief complement
     * 5-> 101 ~ 010
     * 1 <= num < 2^31
     * @param num
     * @return int
     */
    int findComplement(int num)
    {
        vector<int> arr;
        // creating binary array representation for the number
        while (num)
        {
            arr.push_back(num % 2);
            num /= 2;
        }
        int sz = arr.size();
        // Since, we are retrieving bits in backward fashion so we need to reverse it.
        reverse(arr.begin(), arr.end());
        // switching bit values
        for (int i = 0; i < sz; ++i)
        {
            arr[i] = !arr[i];
        }
        long long t = 1;
        // converting our above array into decimal form.
        for (int i = sz - 1; i >= 0; --i)
        {
            num += arr[i] * t;
            t *= 2;
        }
        return num;
    }

    int findComplement_2(int num)
    {
        // counting bits
        int bitCounts = floor(log2(num)) + 1;
        cout << bitCounts << endl;
        // left shifting to make all bits set.
        long ones = (long(1 << int(floor(log2(num)) + 1)) - 1);
        // XOR operator does our work here to complement the value.
        // -2^32 -1 integer overflow
        return int(long(1 << int(floor(log2(num)) + 1)) - 1) ^ num;
    }

    /**
     * @brief Here, floor(log2(num))+1 gives us the number of bits in integer num.
     * The maximum value obtained with this number of bits is pow(2,no of bits)-1.
     *
     * @param num
     * @return int
     */
    int findComplement_3(int num)
    {
        return (pow(2, floor(log2(num)) + 1) - 1) - num;
    }
};

int main(int argc, char const *argv[])
{
    /**
     * @brief test-set
     * 2147483647 -0
     * -2147483647
     * 0 0
     * -1
     */

    Solution solution;
    cout << solution.findComplement(0) << endl;
    return 0;
}
